package MonotonicStack2;

import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class trap_ {

  // 求每个柱子右边第一个比他大的和左边第一个比他大的柱子
  public int trap(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int left;
    int right = 0;
    int sum = 0;
    int middle = 0;
    stack.push(0);
    // 如果height[i] <= height[stack.peek()], 则将height[i]入栈
    for (int i = 1; i < height.length; i++) {
      if (height[stack.peek()] >= height[i]){
        stack.push(height[i]);
      }
      else{
        while(!stack.isEmpty() && height[i] > height[stack.peek()]){
          int H = stack.pop();
          if (!stack.isEmpty()){
            middle = height[H];
            right = height[i];
            left = height[stack.peek()];
            sum += (i - stack.peek() - 1) * Math.min(right,left) - middle;
          }
        }
      }
    }
    return sum;
  }
}
